package datastructure.linkedlist;

/**
 *
 * @author Lei
 */
public class RemoveDuplicate {

    // without using additonal memory
    public static Node removeDuplicate(Node p) {
        if (p == null) {
            return null;
        }

        Node head = p;
        Node tail = p;
        while ( p.next != null) {
            int curValue = p.next.value;
            Node runNode = head;
            boolean bFound = false;
            while (runNode != p.next) {
                if (runNode.value == curValue) {
                    bFound = true;
                    break;
                }
                runNode = runNode.next;
            }

            if (!bFound) {
                tail.next = p.next;
                tail = p.next;
            }
            p = p.next;
        }

        return head;
    }

    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(2);
        Node n4 = new Node(4);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;

        Node result = RemoveDuplicate.removeDuplicate(n1);

        while (result != null) {
            System.out.println(result.value);
            result = result.next;
        }
    }
}
